Gophers

Memory limit: 128 MB

Dick Dastardly wants to bedevil poor Bytean gophers. These nice little creatures live in holes in the upper parts of High Bytemountains.

Dick has found a mountain ridge with gopher holes located along a straight line (for simplicity, we index the holes from 1 to , from west to east). Dick plans to torture gophers using rock & roll music. He has bought CD players, put a different Bytels' album in each of them and arranged the CD players along the ridge. The music from a CD player disturbs gophers located in holes distant by at most meters from it.

Feeling troubled, the gophers asked you to check in which holes they will not be able to sleep well during this winter. But now Dick Dastardly wants to make even more mess...

He will move the CD players from time to time. The gophers were able to steal Dick's secret plan and now they know precisely that on the morning of the -th day Dick will take the CD player located meters from the hole number 1 and will put it at a point located meters from that hole. Help the gophers and count the number of holes in which they will not be able to fall asleep after each such operation.

Input

The first line of input contains four integers , , and (, , ) representing the number of gophers' holes, the number of Dick's CD players, the number of days and the range of a CD player, respectively.

The second line of input contains integers () denoting the distances of the holes from the hole number 1.

The third line contains integers () denoting the distances of the consecutive CD players from the hole number 1. All the CD players are located to the east of this hole.

Next, lines follow. The -th of these lines contains two integers and (, ) meaning that in the beginning of the -th day Dick is going to move the CD player located meters from the hole number 1 to the point located meters to the east from that hole. You may assume that before every such operation there is a CD player at the position and there are no CD players at the position .

Output

Your program should output lines. The line number (for ) should contain one integer representing the number of holes in which no gopher would be able to sleep well during the night before the -th Dick's operation. The last line should contain this number after the last Dick's operation.

Example

For the input data:

5 3 4 1
2 5 6 11
2 4 8
2 1
4 10
8 6
1 8

the correct result is:

2
3
3
5
3

Task author: Jakub Radoszewski.